{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Superposition Kata Workbook, Part 2\n",
    "\n",
    "The [Superposition Kata Workbook, Part 1](./Workbook_Superposition.ipynb) includes the solutions of kata tasks 1 - 7.  Part 2 continues the explanations for the rest of the tasks."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To begin, first prepare this notebook for execution (if you skip this step, you'll get \"Syntax does not match any known patterns\" error when you try to execute Q# code in the next cells):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "%package Microsoft.Quantum.Katas::0.10.1911.1607"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> The package versions in the output of the cell above should always match. If you are running the Notebooks locally and the versions do not match, please install the IQ# version that matches the version of the `Microsoft.Quantum.Katas` package.\n",
    "> <details>\n",
    "> <summary><u>How to install the right IQ# version</u></summary>\n",
    "> For example, if the version of `Microsoft.Quantum.Katas` package above is 0.1.2.3, the installation steps are as follows:\n",
    ">\n",
    "> 1. Stop the kernel.\n",
    "> 2. Uninstall the existing version of IQ#:\n",
    ">        dotnet tool uninstall microsoft.quantum.iqsharp -g\n",
    "> 3. Install the matching version:\n",
    ">        dotnet tool install microsoft.quantum.iqsharp -g --version 0.1.2.3\n",
    "> 4. Reinstall the kernel:\n",
    ">        dotnet iqsharp install\n",
    "> 5. Restart the Notebook.\n",
    "> </details>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a name=\"superposition-of-all-even-or-all-odd-numbers\"></a>Task 10. Superposition of all even or all odd numbers.\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "1. $N$ ($N \\ge 1$) qubits in the $|0 \\dots 0\\rangle$ state (stored in an array of length $N$).\n",
    "2. A boolean `isEven`.\n",
    "\n",
    "**Goal:**  Prepare a superposition of all *even* numbers if `isEven` is `true`, or of all *odd* numbers if `isEven` is `false`.  \n",
    "A basis state encodes an integer number using [big-endian](https://en.wikipedia.org/wiki/Endianness) binary notation: state $|01\\rangle$ corresponds to the integer $1$, and state $|10 \\rangle$ - to the integer $2$.  \n",
    "\n",
    "> For example, for $N = 2$ and `isEven = false` you need to prepare superposition $\\frac{1}{\\sqrt{2}} \\big (|01\\rangle + |11\\rangle\\big )$,  \n",
    "and for $N = 2$ and `isEven = true` - superposition $\\frac{1}{\\sqrt{2}} \\big (|00\\rangle + |10\\rangle\\big )$.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Let’s look at some examples of basis states to illustrate the binary numbering system. \n",
    "\n",
    "The 4 basis states on $N = 2$ qubits can be split in two columns, where the left column represents the basis states that form the required superposition state for `isEven = false` and the right column - the basis states that form the required superposition state for `isEven = true`:\n",
    "\n",
    "<img src=\"./img/Task10_1.png\" width=\"400\">\n",
    " \n",
    "If we do the same basis state split for $N = 3$ qubits, the pattern becomes more obvious:\n",
    " \n",
    "<img src=\"./img/Task10_2.png\" width=\"400\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The two leftmost qubits go through all possible basis states for `isEven = false` and for `isEven = true`, and the rightmost qubit stays in the $|1\\rangle$ state for `isEven = false` and in the $|0\\rangle$ state for `isEven = true`. \n",
    "\n",
    "A quick sanity check for $N = 4$ qubits re-confirms the pattern:\n",
    " \n",
    "<img src=\"./img/Task10_3.png\" width=\"400\">\n",
    " \n",
    "Again, the three leftmost qubits go through all possible basis states in both columns, and the rightmost qubit stays in the same state in each column. \n",
    "\n",
    "The solution is to put all qubits except the rightmost one into an equal superposition (similar to what we did in Task 9) and to set the rightmost qubit to $|0\\rangle$ or $|1\\rangle$ depending on the `isEven` flag, using the X operator to convert $|0\\rangle$ to $|1\\rangle$ if `isEven = false`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T10_EvenOddNumbersSuperposition_Test\n",
    "\n",
    "operation EvenOddNumbersSuperposition (qs : Qubit[], isEven : Bool) : Unit is Adj {\n",
    "    let N = Length(qs);\n",
    "    for (i in 0 .. N-2) {\n",
    "        H(qs[i]);\n",
    "    }\n",
    "    // for odd numbers, flip the last bit to 1\n",
    "    if (not isEven) {\n",
    "        X(qs[N-1]);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 10 of the Superposition kata.](./Superposition.ipynb#superposition-of-all-even-or-all-odd-numbers)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solutions to the rest of the tasks coming up soon...*"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
